#define _CRT_SECURE_NO_WARNINGS 1


#include <iostream>
using namespace std;
#include <vector>
#include<algorithm>
class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        return nums[n / 2];
    }
};

class Solution {
public:
    string intToRoman(int num)
    {
        vector<pair<int, string>> trans;
        trans.push_back({ 1000,"M" });
        trans.push_back({ 900,"CM" });
        trans.push_back({ 500,"D" });
        trans.push_back({ 400,"CD" });
        trans.push_back({ 100,"C" });
        trans.push_back({ 90,"XC" });
        trans.push_back({ 50,"L" });
        trans.push_back({ 40,"XL" });
        trans.push_back({ 10,"X" });
        trans.push_back({ 9,"IX" });
        trans.push_back({ 5,"V" });
        trans.push_back({ 4,"IV" });
        trans.push_back({ 1,"I" });
        string ret;
        for (auto& [dig, str] : trans)
        {
            while (num >= dig)
            {
                num -= dig;
                ret += str;
            }
        }
        return ret;
    }
};